package leetcode;

/**
 * @author: Shelly
 * @create: 2023-01-02 15:21:49
 * @describe: 算法题：70.爬楼梯【简单】
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 注意：给定 n 是一个正整数。
 * 示例 1：
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 * 示例 2：
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶"
 */
public class ClimbStairs {
    public static void main(String[] args) {
        ClimbStairs climbStairs = new ClimbStairs();
        System.out.println(climbStairs.climbStairs(45));

        System.out.println("正确答案：" + climbStairs.climbStairs(14));
        System.out.println("我的错误答案：" + climbStairs.climbStairs_me(14));
    }

    /**
     * 正确答案:第n个台阶只能从第n-1或者n-2个上来。到第n-1个台阶的走法 + 第n-2个台阶的走法 = 到第n个台阶的走法，已经知道了第1个和第2个台阶的走法，一路加上去
     *
     * 视频讲解-动态规划：https://www.bilibili.com/video/BV13Q4y197Wg/?vd_source=1cd30b0cf474457fddd2be979e1bdc7e
     * 文档说明：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E4%BB%80%E4%B9%88%E6%98%AF%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
     * 斐波拉契数列
     * 思考 Java的话因为返回值为int，n=46时，结果会溢出，因此n < 46
     *     45 ：1836311903
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n == 1){return 1;}
        if(n == 2){return 2;}
        int a = 1, b = 2, temp;
        for(int i = 3; i <= n; i++){
            temp = a;
            a = b;
            b = temp + b;
        }
        return b;
    }

    /*******************************************   我的解答【错的】   ***************************************************************************************************
     * 12 / 45 个通过测试用例
     * 35录入结果错误
     * @param n
     * @return
     */
    public int climbStairs_me(int n){
        int count = 0;
        for(int x = 0;x <= n;x++)
            for (int y = 0;y <= n ;y++){
                if(x + 2 * y == n){
                    if (x == 0 || y== 0){
                        count++;
                    }else {
                        count = count + getCxxy(x, y);
                    }
                }
            }
        return  count;
    }

    /**
     * 组合C（上x，下x+y）
     * @param x
     * @param y
     * @return
     */
    public int getCxxy(int x,int y){
        return getProduct(x,y)/recursion(x);
    }

    /**
     * 获取乘积：x+y * (x+y-1)...x个数
     * @return
     */
    public int getProduct(int x,int y){
        int sum = x+y;
        int result = 1;
        for(int i = 1;i <= x;i++){
            result = result * sum;
            sum--;
        }
        return result;
    }

    /**
     * x!
     * @return
     */
    public int recursion(int x){
        if (x == 1) return 1;
        return x * recursion(x-1);
    }
}
